package com.xzz.backtrack;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author: hhz
 * @create: 2022-01-10 14:23
 * 46. 全排列
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 **/
public class Permute {
    public static void main(String[] args) {
        System.out.println(permute(new int[]{1,2,3}));
    }
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(nums,new LinkedList<>(),res);
        return res;
    }
    public static void backtrack(int[] nums,LinkedList<Integer> list,List<List<Integer>> res) {
        if(nums.length==list.size()){
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if(list.contains(nums[i])){
                continue;
            }
            list.add(nums[i]);
            backtrack(nums,list,res);
            list.removeLast();
        }


    }
}
